package pers.sloera.leetcode.editor.cn;

import java.util.PriorityQueue;

/**
 * 灌溉花园的最少水龙头数目
 *
 * @author sloera
 * @date 2023-02-21 21:53:23
 */
class MinimumNumberOfTapsToOpenToWaterAGarden {
    public static void main(String[] args) {
        Solution solution = new MinimumNumberOfTapsToOpenToWaterAGarden().new Solution();
        System.out.println(solution.minTaps(7, new int[]{1, 2, 1, 0, 2, 1, 0, 1}));
        // System.out.println(solution.minTaps(5, new int[]{3, 4, 1, 1, 0, 0}));
        // System.out.println(solution.minTaps(3, new int[]{0, 0, 0, 0}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minTaps(int n, int[] ranges) {
            PriorityQueue<Duration> areaQueue = new PriorityQueue<>((x, y) -> {
                // 从最左侧开始
                int compare = Integer.compare(x.start, y.start);
                if (compare == 0) {
                    // 起始相同，长度长的先使用
                    return Integer.compare(y.end - y.start, x.end - x.start);
                }
                return compare;
            });
            for (int i = 0; i < ranges.length; i++) {
                areaQueue.add(new Duration(i - ranges[i], i + ranges[i]));
            }
            int start = 0;
            int ret = 0;
            while (start < n && areaQueue.peek() != null) {
                handleDurationStart(areaQueue, start);
                Duration duration = areaQueue.poll();
                if (duration.start <= start) {
                    start = duration.end;
                    ret++;
                } else {
                    break;
                }
            }
            return start >= n ? ret : -1;
        }

        // 将各区间的起始位置，置为start
        private void handleDurationStart(PriorityQueue<Duration> areaQueue, int start) {
            Duration poll;
            while ((poll = areaQueue.poll()) != null) {
                if (poll.start < start) {
                    poll.start = start;
                    if (poll.end > poll.start) {
                        areaQueue.add(poll);
                    }
                } else {
                    areaQueue.add(poll);
                    break;
                }
            }
        }

        class Duration {
            int start;
            int end;

            public Duration(int start, int end) {
                this.start = start;
                this.end = end;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
